{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Integers to Choose From a Range I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从一个范围内选择最多整数 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>banned</code>&nbsp;和两个整数&nbsp;<code>n</code> 和&nbsp;<code>maxSum</code>&nbsp;。你需要按照以下规则选择一些整数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>被选择整数的范围是&nbsp;<code>[1, n]</code>&nbsp;。</li>\n",
    "\t<li>每个整数 <strong>至多</strong>&nbsp;选择 <strong>一次</strong>&nbsp;。</li>\n",
    "\t<li>被选择整数不能在数组&nbsp;<code>banned</code>&nbsp;中。</li>\n",
    "\t<li>被选择整数的和不超过&nbsp;<code>maxSum</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回按照上述规则 <strong>最多</strong>&nbsp;可以选择的整数数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>banned = [1,6,5], n = 5, maxSum = 6\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>你可以选择整数 2 和 4 。\n",
    "2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>按照上述规则无法选择任何整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>banned = [11], n = 7, maxSum = 50\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。\n",
    "它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= banned.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= banned[i], n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= maxSum &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-integers-to-choose-from-a-range-i](https://leetcode.cn/problems/maximum-number-of-integers-to-choose-from-a-range-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-integers-to-choose-from-a-range-i](https://leetcode.cn/problems/maximum-number-of-integers-to-choose-from-a-range-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,6,5]\\n5\\n6', '[1,2,3,4,5,6,7]\\n8\\n1', '[11]\\n7\\n50']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def captureForts(self, forts: List[int]) -> int:\n",
    "        pre = None\n",
    "        maxCount = 0\n",
    "\n",
    "        for i, n in enumerate(forts):\n",
    "            if n == 1:\n",
    "                if pre is not None and pre[0] == -1:\n",
    "                    maxCount = max(maxCount, i - pre[1] - 1)\n",
    "                pre = (1, i)\n",
    "\n",
    "            elif n == -1:\n",
    "                if pre is not None and pre[0] == 1:\n",
    "                    maxCount = max(maxCount, i - pre[1] - 1)\n",
    "                pre = (-1, i)\n",
    "            else:\n",
    "                continue\n",
    "        return maxCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class FreqStack:\n",
    "    def __init__(self):\n",
    "        self.value_to_count = {}\n",
    "        self.value_to_pop={}\n",
    "        self.maxCount=0\n",
    "\n",
    "    def push(self, val: int) -> None:\n",
    "        self.value_to_count[val] = self.value_to_count.get(val, 0) + 1\n",
    "            # 使用 get 方法获取值对应的列表，如果不存在则使用空列表\n",
    "        value_list = self.value_to_pop.get(self.value_to_count[val], [])\n",
    "        # 将值添加到列表中\n",
    "        value_list.append(val)\n",
    "        # 更新 self.value_to_pop 字典\n",
    "        self.value_to_pop[self.value_to_count[val]] = value_list\n",
    "\n",
    "        self.maxCount=max(self.maxCount,self.value_to_count[val])\n",
    "\n",
    "    def pop(self) -> int:\n",
    "        res=self.value_to_pop[self.maxCount].pop()\n",
    "        self.value_to_count[res]-=1\n",
    "        if len(self.value_to_pop[self.maxCount])==0:\n",
    "            self.maxCount-=1\n",
    "        return res\n",
    "\n",
    "\n",
    "# Your FreqStack object will be instantiated and called as such:\n",
    "# obj = FreqStack()\n",
    "# obj.push(val)\n",
    "# param_2 = obj.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned.sort()\n",
    "        sum = 0\n",
    "        count = 0\n",
    "        it = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if it < len(banned) and i == banned[it]:\n",
    "                while it < len(banned) and i == banned[it]:  # banned可能出现重复数字\n",
    "                    it += 1\n",
    "            else:\n",
    "                sum += i\n",
    "                if sum > maxSum:\n",
    "                    break\n",
    "                else:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ban_nums = [0 for i in range(n+1)]\n",
    "        for num in banned:\n",
    "            if num <= n:\n",
    "                ban_nums[num] = 1\n",
    "        sum = 0\n",
    "        count = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if not ban_nums[i]:\n",
    "                sum += i\n",
    "                if sum > maxSum:\n",
    "                    break\n",
    "                else:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned.append(n+1)\n",
    "        banned.sort()\n",
    "        left = 1\n",
    "        res = 0\n",
    "        for right in banned:\n",
    "            if right - 1 >= left:\n",
    "                m = floor((sqrt(1 + 4 * (maxSum*2-left + left**2))-1)/2.0)\n",
    "                m = min(m, right-1)\n",
    "                s = (m - left + 1)*(left + m)//2\n",
    "                res += m - left + 1\n",
    "                maxSum -= s\n",
    "                if maxSum < m + 1: break\n",
    "            if right > n: break\n",
    "            left = right + 1\n",
    "        return res\n",
    "        # (m-left+1)*(left+m) > 2s\n",
    "        # m**2 - left**2 + m + left > 2s\n",
    "        # m**2 + m > 2s - left + left**2\n",
    "        # (-1+sqrt(1+4(2s-left+left**2))) / 2\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        b = [True] * (n + 1)\n",
    "        for x in banned:\n",
    "            if x <= n:\n",
    "                b[x] = False\n",
    "        res = 0\n",
    "        for x in range(1, n + 1):\n",
    "            if b[x]:\n",
    "                if maxSum < x:\n",
    "                    break\n",
    "                maxSum -= x\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        \n",
    "        nums = [0]*(n+1)\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            nums[i] = i\n",
    "        \n",
    "        for i in range(0, len(banned)):\n",
    "            if banned[i] <= n:\n",
    "                nums[banned[i]] = 0\n",
    "        \n",
    "        count = 0\n",
    "        \n",
    "        sum_ = 0\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            \n",
    "            if nums[i] > 0:\n",
    "                sum_ += nums[i]\n",
    "                count += 1\n",
    "                \n",
    "                if sum_ > maxSum:\n",
    "                    return count - 1\n",
    "            \n",
    "                if sum_ == maxSum:\n",
    "                    return count\n",
    "            \n",
    "        return count\n",
    "        \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        cnt = 0\n",
    "        l = len(banned)\n",
    "        vis = {}\n",
    "        for i in range(l):\n",
    "            vis[banned[i]] = 1\n",
    "        cur = 0\n",
    "        up = min(maxSum + 1, n + 1)\n",
    "        for i in range(1, up):\n",
    "            if i <= n and i not in vis and cur + i <= maxSum:\n",
    "                cnt += 1\n",
    "                cur += i\n",
    "        return cnt\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned = set(banned)\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < n and ans <= maxSum:\n",
    "            i += 1\n",
    "            if i not in banned:\n",
    "                ans += i\n",
    "                if ans <= maxSum:\n",
    "                    count += 1\n",
    "            \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans, s = 0, set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans, s = 0, set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned = set(banned)\n",
    "        rsum = 0\n",
    "        result = 0\n",
    "        for num in range(1,n+1):\n",
    "            if(num not in banned and rsum + num <= maxSum):\n",
    "                result += 1\n",
    "                rsum += num\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        s = set(banned)\n",
    "        sum_ = 0\n",
    "        num = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i > maxSum:\n",
    "                break\n",
    "            if sum_ > maxSum:\n",
    "                return num-1\n",
    "            else:\n",
    "                if i not in s:\n",
    "                    sum_ += i\n",
    "                    num += 1\n",
    "\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans, s = 0, set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned = set(banned)\n",
    "        cnt = 0        \n",
    "        for num in range(1, n+1):\n",
    "            if num not in banned and maxSum - num >=0:\n",
    "               cnt+=1\n",
    "               maxSum -= num \n",
    "\n",
    "        return cnt\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        fh = 0\n",
    "        jh = set(banned)\n",
    "        for i in range(1, n+1):\n",
    "            if i not in jh:\n",
    "                if i > maxSum:\n",
    "                    return fh\n",
    "                else:\n",
    "                    maxSum -= i\n",
    "                    fh += 1\n",
    "        return fh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:\n",
    "        cnt = 0\n",
    "        total = 0\n",
    "        banned = set(banned)\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            if i not in banned and maxSum>=total+i:\n",
    "                total+=i\n",
    "                cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        sum_ = 0\n",
    "        cnt = 0\n",
    "        banned = set(banned)\n",
    "        for i in range(1, n+1):\n",
    "            if i not in banned:\n",
    "                sum_ += i\n",
    "                if sum_ <= maxSum:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        h = 0\n",
    "        fh = 0\n",
    "        jh = set(banned)\n",
    "        for i in range(1, n+1):\n",
    "            if i not in jh:\n",
    "                if h+i > maxSum:\n",
    "                    return fh\n",
    "                else:\n",
    "                    h += i\n",
    "                    fh += 1\n",
    "        return fh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned_dict = dict()\n",
    "        for banned_num in banned:\n",
    "            banned_dict[banned_num] = 1\n",
    "        num_candidate = list()\n",
    "        cur_sum = 0\n",
    "        for num in range(1, n+1):\n",
    "            if num not in banned_dict:\n",
    "                tmp_sum = cur_sum + num\n",
    "                if tmp_sum > maxSum:\n",
    "                    break\n",
    "                else:\n",
    "                    cur_sum += num\n",
    "                    num_candidate.append(num)\n",
    "\n",
    "        return len(num_candidate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        sum_ = 0\n",
    "        banned = set(banned)\n",
    "        for i in range(1,n+1):\n",
    "            if i not in banned and i <= maxSum:\n",
    "                maxSum -= i\n",
    "                sum_ += 1\n",
    "        return sum_\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans = s = 0\n",
    "        banned = set(banned)\n",
    "        for i in range(1, n+1):\n",
    "            if i not in banned:\n",
    "                if s + i <= maxSum:\n",
    "                    s += i\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    return ans\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        bs = set(banned)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i not in bs:\n",
    "                ans += i \n",
    "                if ans <= maxSum:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    # print(ans)\n",
    "                    return cnt\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        t = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i not in banned:\n",
    "                maxSum-=i\n",
    "                t+=1\n",
    "            if maxSum==0:\n",
    "                break\n",
    "            if maxSum<0:\n",
    "                t-=1\n",
    "                break\n",
    "        return t'''\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans, s = 0, set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned = sorted(set(banned))\n",
    "        i = 0\n",
    "        x = 1\n",
    "        s = 0\n",
    "        cnt = 0\n",
    "        while x <= n:\n",
    "            if i < len(banned) and x == banned[i]:\n",
    "                i += 1\n",
    "            else:\n",
    "                if s + x <= maxSum:\n",
    "                    s += x\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "            x += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ban = set(banned)\n",
    "        ans = s = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in ban:\n",
    "                s += i \n",
    "                if s <= maxSum:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        s = set(banned)\n",
    "        ans = 0\n",
    "        now = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i not in s and now + i <= maxSum:\n",
    "                now += i\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:\n",
    "        cnt = 0\n",
    "        total = 0\n",
    "        banned = set(banned)\n",
    "        \n",
    "        for i in range(1,n+1): # iteration should start from 1 not 2\n",
    "            if i not in banned and maxSum>=total+i:\n",
    "                cnt+=1\n",
    "                total+=i\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned = set([x for x in banned if x <=n])\n",
    "        total = int((1 + n) * n / 2) - sum(banned)\n",
    "        res = n - len(banned)\n",
    "        for i in range(n, 0, -1):\n",
    "            if total <= maxSum:\n",
    "                return res\n",
    "            else:\n",
    "                if i not in banned:\n",
    "                    total -= i\n",
    "                    res -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans=0\n",
    "        num_set=set(banned)\n",
    "        for i in range(1,n+1):\n",
    "            if i>maxSum:\n",
    "                break\n",
    "            else:\n",
    "                if i not in num_set:\n",
    "                    maxSum-=i\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans, s = 0, set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        i = 1\n",
    "        s = set(banned)\n",
    "        count = 0\n",
    "        total = 0\n",
    "        while i<=n and total<=maxSum:\n",
    "            if i not in s and total+i<=maxSum:\n",
    "                total += i\n",
    "                count += 1\n",
    "            i += 1\n",
    "        return count \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        seen = set(banned)\n",
    "\n",
    "        sum_ = 0\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i not in seen:\n",
    "                sum_ += i\n",
    "                if sum_ > maxSum:\n",
    "                    break\n",
    "                \n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans=0\n",
    "        num_set=set(banned)\n",
    "        for i in range(1,n+1):\n",
    "            if i>maxSum:\n",
    "                break\n",
    "            else:\n",
    "                if i not in num_set:\n",
    "                    maxSum-=i\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        new_banned = sorted(list(set(filter(lambda x:x<=n, banned))))\n",
    "        new_banned.append(n+1)\n",
    "        i = sum = asn = 0\n",
    "        sum = 0\n",
    "        for x in range(1, n+1):\n",
    "            if sum > maxSum:\n",
    "                return 0 if asn == 0 else asn - 1\n",
    "            elif new_banned[i] == x:\n",
    "                i += 1\n",
    "                pass\n",
    "            else:\n",
    "                sum += x\n",
    "                asn += 1\n",
    "        return asn - 1 if sum > maxSum else asn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        cnt = 0\n",
    "        s = set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum:\n",
    "                break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        s = set(banned)\n",
    "        S = 0\n",
    "        cnt = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i not in s:\n",
    "                if S + i <= maxSum:\n",
    "                    S += i\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans, s = 0, set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned = set(banned)\n",
    "        total = cnt = 0\n",
    "        for x in range(1, n + 1):\n",
    "            if x not in banned:\n",
    "                total += x\n",
    "                cnt += 1\n",
    "                if total > maxSum:\n",
    "                    cnt -= 1\n",
    "                    break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, e: List[int], n: int, s: int) -> int:\n",
    "        e=set(e)\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            if i not in e:\n",
    "                if s<i:\n",
    "                    break\n",
    "                s-=i\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        cur_sum = 0\n",
    "        res = 0\n",
    "        banned_set = set(banned)\n",
    "        for i in range(1, n+1):\n",
    "            if i in banned_set:\n",
    "                continue\n",
    "            cur_sum += i\n",
    "            if cur_sum > maxSum:\n",
    "                return res\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans, s = 0, set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        x=1\n",
    "        ans=0\n",
    "        tot=0\n",
    "        s=set(banned)\n",
    "        while x<=n and ans<=maxSum:\n",
    "            if not x in s:\n",
    "                ans+=x\n",
    "                tot+=1\n",
    "            x+=1\n",
    "        if ans<=maxSum:\n",
    "            tot+=1\n",
    "        return tot-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        h = 0\n",
    "        fh = 0\n",
    "        jh = set(banned)\n",
    "        for i in range(1, n+1):\n",
    "            if i not in jh:\n",
    "                if h+i > maxSum:\n",
    "                    return fh\n",
    "                else:\n",
    "                    h += i\n",
    "                    fh += 1\n",
    "        return fh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned = set(banned)\n",
    "        rsum = 0\n",
    "        result = 0\n",
    "        for num in range(1,n+1):\n",
    "            if(num not in banned and rsum + num <= maxSum):\n",
    "                result += 1\n",
    "                rsum += num\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        sum1 = 0\n",
    "        count = 0\n",
    "        banned = set(banned)\n",
    "        for i in range(1,n+1):\n",
    "            if i not in banned:\n",
    "                if sum1 +i <= maxSum:\n",
    "                    sum1+=i\n",
    "                    count+=1\n",
    "                else:\n",
    "                    break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans, s = 0, set(banned)\n",
    "        for i in range(1, n + 1):\n",
    "            if i > maxSum: break\n",
    "            if i not in s:\n",
    "                maxSum -= i\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        res = s = 0\n",
    "        banned = set(banned)\n",
    "        for i in range(1, n+1):\n",
    "            if i not in banned:\n",
    "                if s + i > maxSum:\n",
    "                    break\n",
    "                s += i \n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned=list(set(banned))\n",
    "        banned.sort()\n",
    "        banpre=[0]\n",
    "        for c in banned:\n",
    "            banpre.append(banpre[-1]+c)\n",
    "        ss=sum(banned)\n",
    "        l,r=0,n\n",
    "        # 检查当前的最大x去除banned前缀之后\n",
    "        def ck(x):\n",
    "            j=bisect_right(banned,x)\n",
    "            return (1+x)*x//2-banpre[j]>maxSum\n",
    "        while l<=r:\n",
    "            x=l+(r-l)//2\n",
    "            if ck(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        j=bisect_right(banned,l-1)\n",
    "        return (l-1)-j\n",
    "\n",
    "\n",
    "    # def maxCount_ok(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "    #     ban = set(banned)\n",
    "    #     ss=0\n",
    "    #     ans=0\n",
    "    #     for i in range(1,1+n):\n",
    "    #         if ss+i>maxSum:\n",
    "    #             break\n",
    "    #         if i in ban:\n",
    "    #             continue\n",
    "    #         ss+=i\n",
    "    #         ans+=1\n",
    "    #     return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        i = 1\n",
    "        s = set(banned)\n",
    "        count = 0\n",
    "        total = 0\n",
    "        while i<=n and total<=maxSum:\n",
    "            if i not in s and total+i<=maxSum:\n",
    "                total += i\n",
    "                count += 1\n",
    "            i += 1\n",
    "        return count \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        # 创建一个集合，包含从1到n的所有整数\n",
    "        available_nums = set(range(1, n + 1))\n",
    "        \n",
    "        # 从集合中移除被禁止的数字\n",
    "        for b in banned:\n",
    "            available_nums.discard(b)\n",
    "        \n",
    "        # 对剩余数字进行排序\n",
    "        available_nums = sorted(list(available_nums))\n",
    "        \n",
    "        count = 0\n",
    "        total_sum = 0\n",
    "        \n",
    "        # 从小到大开始选择整数并加和，直到超过maxSum为止\n",
    "        for num in available_nums:\n",
    "            if total_sum + num <= maxSum:\n",
    "                total_sum += num\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return count\n",
    "\n",
    "# 测试用例\n",
    "solution = Solution()\n",
    "print(solution.maxCount([1,6,5], 5, 6))  # 输出2\n",
    "print(solution.maxCount([1,2,3,4,5,6,7], 8, 1))  # 输出0\n",
    "print(solution.maxCount([11], 7, 50))  # 输出7\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        m_arr = []\n",
    "        res = 0\n",
    "        banned = list(set(banned))\n",
    "        banned.sort()\n",
    "        \n",
    "        short = maxSum if maxSum < n else n\n",
    "        for i,k in enumerate(banned):\n",
    "            if k > short:\n",
    "                banned = banned[0:i + 1]\n",
    "                break\n",
    "\n",
    "\n",
    "        for i in range(1,short + 1):\n",
    "            if not i in banned:\n",
    "                m_arr.append(i)\n",
    "\n",
    "                \n",
    "        for i in m_arr:\n",
    "            if i <= maxSum:\n",
    "                maxSum -=i\n",
    "                res +=1\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned=list(set(banned))\n",
    "        banned.sort()\n",
    "        banpre=[0]\n",
    "        for c in banned:\n",
    "            banpre.append(banpre[-1]+c)\n",
    "        ss=sum(banned)\n",
    "        l,r=0,n\n",
    "        l=bisect_right(range(n+1), maxSum, key=lambda x:(1+x)*x//2-banpre[bisect_right(banned,x)])\n",
    "        j=bisect_right(banned,l-1)\n",
    "        return (l-1)-j\n",
    "\n",
    "\n",
    "\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        banned=list(set(banned))\n",
    "        banned.sort()\n",
    "        banpre=[0]\n",
    "        for c in banned:\n",
    "            banpre.append(banpre[-1]+c)\n",
    "        ss=sum(banned)\n",
    "        l,r=0,n\n",
    "        def ck(x):\n",
    "            j=bisect_right(banned,x)\n",
    "            return (1+x)*x//2-banpre[j]>maxSum\n",
    "        while l<=r:\n",
    "            x=l+(r-l)//2\n",
    "            if ck(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        j=bisect_right(banned,l-1)\n",
    "        return (l-1)-j\n",
    "\n",
    "\n",
    "    def maxCount_ok(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ban = set(banned)\n",
    "        ss=0\n",
    "        ans=0\n",
    "        for i in range(1,1+n):\n",
    "            if ss+i>maxSum:\n",
    "                break\n",
    "            if i in ban:\n",
    "                continue\n",
    "            ss+=i\n",
    "            ans+=1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        m_arr = []\n",
    "        res = 0\n",
    "        banned = list(set(banned))\n",
    "        banned.sort()\n",
    "        \n",
    "        short = maxSum if maxSum < n else n\n",
    "        for i,k in enumerate(banned):\n",
    "            if k > short:\n",
    "                banned = banned[0:i + 1]\n",
    "\n",
    "\n",
    "        for i in range(1,short + 1):\n",
    "            if not i in banned:\n",
    "                m_arr.append(i)\n",
    "\n",
    "                \n",
    "        for i in m_arr:\n",
    "            if i <= maxSum:\n",
    "                maxSum -=i\n",
    "                res +=1\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        m_arr = []\n",
    "        res = 0\n",
    "        banned = list(set(banned))\n",
    "        banned.sort()\n",
    "        \n",
    "        short = maxSum if maxSum < n else n\n",
    "        for i,k in enumerate(banned):\n",
    "            if k > short:\n",
    "                banned = banned[0:i + 1]\n",
    "\n",
    "\n",
    "        for i in range(1,short + 1):\n",
    "            if not i in banned:\n",
    "                m_arr.append(i)\n",
    "\n",
    "                \n",
    "        for i in m_arr:\n",
    "            if i <= maxSum:\n",
    "                maxSum -=i\n",
    "                res +=1\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        x = list(set(range(1, n + 1)).difference(set(banned)))\n",
    "        x.sort()\n",
    "        rs = 0\n",
    "        s = 0\n",
    "        for xx in x:\n",
    "            if s + xx <= maxSum:\n",
    "                s += xx\n",
    "                rs += 1\n",
    "            else:\n",
    "                break;\n",
    "        return rs\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        res,ans = 0,0\n",
    "        tem = list(set([i for i in range(1,n+1)]) - set(banned))\n",
    "        tem = sorted(tem)\n",
    "        for i in tem:\n",
    "            if ans + i <= maxSum:\n",
    "                ans+=i\n",
    "                res +=1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        chosen, index = [], 0\n",
    "        banned = list(set(banned))\n",
    "        banned.sort()\n",
    "        for i in range(1, n+1):\n",
    "            if i == banned[index]:\n",
    "                index += 1\n",
    "                index = min(index, len(banned)-1)\n",
    "            else:\n",
    "                chosen.append(i)\n",
    "        \n",
    "        ans, right = 0, len(chosen)-1\n",
    "        a, ans = sum(chosen), len(chosen)\n",
    "        while a > maxSum:\n",
    "            a -= chosen.pop()\n",
    "            ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        selectedlist=list(set(range(1,n+1))-set(banned))\n",
    "        selectedlist.sort()\n",
    "        sumresult=0\n",
    "        sumconut=0\n",
    "        for i in range(len(selectedlist)):\n",
    "            sumresult+=selectedlist[i]\n",
    "            if sumresult>maxSum:\n",
    "               break\n",
    "            else:\n",
    "               sumconut+=1\n",
    "\n",
    "        return sumconut\n",
    "        #print(sumconut)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        tmp = 0\n",
    "        ans = []\n",
    "        st = set([i for i in range(1, n+1)]) - set(banned)\n",
    "        st = list(st)\n",
    "        st.sort()\n",
    "        for i in st:\n",
    "                tmp += i\n",
    "                \n",
    "                if tmp > maxSum:\n",
    "                    break\n",
    "                ans.append(i)\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        \"\"\"\n",
    "        思路：\n",
    "        找到1到n的整数，放在一个变量raw中；\n",
    "        raw与banned进行差集运算，给变量raw1；\n",
    "        使用fow循环，raw1中元素求和，如果不超过maxsum则输出len，超过则i减1继续求和比较，一直到找到和小于maxsum的个数————要优先排序，从最大的值开始减，从而保证渠道的整数个数最多\n",
    "        \"\"\"\n",
    "        raw = list(range(1,n+1))\n",
    "        # print (\"构造1到n的列表：\",raw)\n",
    "        raw1 = list(set(raw) - set(banned))\n",
    "        # print (\"和banned计算完差集的列表：\",raw1)\n",
    "        raw2 = sorted(raw1)\n",
    "        # print(\"排序之后的列表\",raw2)\n",
    "        raw2.reverse()\n",
    "        # print(\"倒序之后的列表：\", raw2)\n",
    "        list(set(raw2))\n",
    "        n = len(raw2)\n",
    "        # print(\"剔除重复值后的列表\", raw2)\n",
    "        for i in range(0, n):\n",
    "            # raw3 = raw2\n",
    "            print(i)\n",
    "            print(n)\n",
    "            if sum(raw2) <= maxSum:\n",
    "                print(\"和小于给定的限制\")\n",
    "                break\n",
    "            else:\n",
    "                print(\"和大于给定的限制\")\n",
    "                del raw2[0]\n",
    "                print(\"剔除第%d个元素\" % i)\n",
    "            # print(raw2)\n",
    "        return len(raw2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        ans = 0\n",
    "        tem = list(set([i for i in range(1,n+1)]) - set(banned))\n",
    "\n",
    "        while sum(tem) > maxSum:\n",
    "            tem.remove(max(tem))\n",
    "        return len(tem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n",
    "        \"\"\"\n",
    "        思路：\n",
    "        找到1到n的整数，放在一个变量raw中；\n",
    "        raw与banned进行差集运算，给变量raw1；\n",
    "        使用fow循环，raw1中元素求和，如果不超过maxsum则输出len，超过则i减1继续求和比较，一直到找到和小于maxsum的个数————要优先排序，从最大的值开始减，从而保证渠道的整数个数最多————>修改为：边加边求和\n",
    "        \"\"\"\n",
    "        raw = list(range(1,n+1))\n",
    "        raw1 = list(set(raw) - set(banned))\n",
    "        raw2 = sorted(raw1)\n",
    "        n = len(raw2)\n",
    "        sum = 0\n",
    "        i = 0\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        for i in range(0, n):\n",
    "            print(i)\n",
    "            # print(n)\n",
    "            # sum = 0\n",
    "            sum += raw2[i]\n",
    "            print(sum)\n",
    "            # if sum <= maxSum:\n",
    "            #     print(\"和小于给定的限制\")\n",
    "            if sum > maxSum:\n",
    "                print(\"和大于给定的限制\")\n",
    "                return i\n",
    "                break\n",
    "        return (i + 1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
